package org.basis.algorithm.promote;

import org.basis.algorithm.promote.common.TreeNode;

import java.util.ArrayDeque;

/**
 * 求树中两个节点的最大距离
 *
 * @author Mr_wenpan@163.com 2022/01/11 21:58
 */
public class MaxDistanceInTree {

    public static void main1(String[] args) {
        TreeNode<Integer> head1 = new TreeNode<Integer>(1);
        head1.left = new TreeNode<Integer>(2);
        head1.right = new TreeNode<Integer>(3);
        head1.left.left = new TreeNode<Integer>(4);
        head1.left.right = new TreeNode<Integer>(5);
        head1.right.left = new TreeNode<Integer>(6);
        head1.right.right = new TreeNode<Integer>(7);
        head1.left.left.left = new TreeNode<Integer>(8);
        head1.right.left.right = new TreeNode<Integer>(9);
        System.out.println(maxDistance(head1));

        TreeNode<Integer> head2 = new TreeNode<Integer>(1);
        head2.left = new TreeNode<Integer>(2);
        head2.right = new TreeNode<Integer>(3);
        head2.right.left = new TreeNode<Integer>(4);
        head2.right.right = new TreeNode<Integer>(5);
        head2.right.left.left = new TreeNode<Integer>(6);
        head2.right.right.right = new TreeNode<Integer>(7);
        head2.right.left.left.left = new TreeNode<Integer>(8);
        head2.right.right.right.right = new TreeNode<Integer>(9);
        System.out.println(maxDistance(head2));

    }

    /**
     * 给定一个头节点，求这棵树上距离最远的两个点的距离
     */
    public static int maxDistance(TreeNode<Integer> head) {
        if (head == null) {
            return 0;
        }
        return process(head).maxDistance;
    }

    /**
     * 递归函数，递归处理左右子树
     */
    public static Result process(TreeNode<Integer> head) {
        // base case
        if (head == null) {
            return new Result(0, 0);
        }
        Result leftRes = process(head.left);
        Result rightRes = process(head.right);
        // 整理左右子树的信息
        int leftHigh = leftRes.high;
        int rightHigh = rightRes.high;
        int heigh = Math.max(leftHigh, rightHigh) + 1;
        // 左右树中距离最大的
        int childMax = Math.max(leftRes.maxDistance, rightRes.maxDistance);
        // 左右树高度之和+1
        int includeHead = leftHigh + rightHigh + 1;
        int maxDistance = Math.max(includeHead, childMax);

        // 构造自己的信息向上返回
        return new Result(heigh, maxDistance);
    }

    static class Result {
        public int high;
        public int maxDistance;

        public Result(int high, int maxDistance) {
            this.high = high;
            this.maxDistance = maxDistance;
        }
    }

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            value = data;
        }
    }

    public static int maxDistance(Node head) {
        int[] record = new int[1];
        return process(head).maxDistance;
    }

    public static class ReturnType {
        public int maxDistance;
        public int h;

        public ReturnType(int m, int h) {
            maxDistance = m;
            this.h = h;
        }
    }

    public static ReturnType process(Node head) {
        if (head == null) {
            return new ReturnType(0, 0);
        }
        ReturnType leftReturnType = process(head.left);
        ReturnType rightReturnType = process(head.right);
        int includeHeadDistance = leftReturnType.h + 1 + rightReturnType.h;
        int p1 = leftReturnType.maxDistance;
        int p2 = rightReturnType.maxDistance;
        int resultDistance = Math.max(Math.max(p1, p2), includeHeadDistance);
        int hitself = Math.max(rightReturnType.h, leftReturnType.h) + 1;
        return new ReturnType(resultDistance, hitself);
    }

    public static void main(String[] args) {
        Node head1 = new Node(1);
        head1.left = new Node(2);
        head1.right = new Node(3);
        head1.left.left = new Node(4);
        head1.left.right = new Node(5);
        head1.right.left = new Node(6);
        head1.right.right = new Node(7);
        head1.left.left.left = new Node(8);
        head1.right.left.right = new Node(9);
        System.out.println(maxDistance(head1));

        Node head2 = new Node(1);
        head2.left = new Node(2);
        head2.right = new Node(3);
        head2.right.left = new Node(4);
        head2.right.right = new Node(5);
        head2.right.left.left = new Node(6);
        head2.right.right.right = new Node(7);
        head2.right.left.left.left = new Node(8);
        head2.right.right.right.right = new Node(9);
        System.out.println(maxDistance(head2));

        String str = smallestSubsequence("cdacdcbc");
        System.out.println(str);
    }

    public static String smallestSubsequence(String s) {

        if (s == null || s.length() <= 1) {
            return s;
        }

        char[] chars = s.toCharArray();
        // 单调递增的栈
        ArrayDeque<Character> stack = new ArrayDeque<Character>();
        // 记录每个字符的出现次数(由于全是小写字母，所以26个长度就够了)
        int[] count = new int[26];
        for (int i = 0; i < chars.length; i++) {
            // 获取当前字符在数组中的位置
            int index = chars[i] - 'a';
            // 出现次数++
            count[index]++;
        }

        for (int j = 0; j < chars.length; j++) {
            while (!stack.isEmpty()
                    && stack.peekLast() >= chars[j]
                    && count[stack.peekLast() - 'a'] > 1) {
                stack.pollLast();
                count[chars[j] - 'a']--;
            }
            // 将i位置的字符加入栈
            stack.addLast(chars[j]);
        }

        StringBuilder sb = new StringBuilder();

        while (!stack.isEmpty()) {
            sb.append(stack.pollFirst());
        }

        return sb.toString();
    }
}
